// 动态规划5
// class Solution {
// public:
//     int uniquePaths(int m, int n) {
//         vector<vector<int>> dp(m,vector<int>(n,1));
//         if(m == 1 || n == 1) return 1;
//         for(int i = 1 ; i < m ; i++)
//         {
//             for(int j = 1 ; j < n ; j++)
//                 dp[i][j] = dp[i-1][j] + dp[i][j-1];
//         }

//         return dp[m-1][n-1];
//     }
// };

// 动态规划6
// class Solution {
// public:
//     int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
//         int m = obstacleGrid.size(), n = obstacleGrid[0].size();
//         vector<vector<int>> dp(m+1,vector<int>(n+1,0));
//         dp[0][1] = 1;

//         for(int i = 1 ; i <= m ; i++)
//         {
//             for(int j = 1 ; j <= n ; j++)
//             {
//                 if(obstacleGrid[i-1][j-1] == 1)
//                 {
//                     dp[i][j] = 0;
//                     continue;
//                 }
//                 dp[i][j] = dp[i-1][j] + dp[i][j-1];
//             }
//         }

//         return dp[m][n];
//     }
// };

// 动态规划7
// class Solution {
// public:
//     int jewelleryValue(vector<vector<int>>& frame) {
//         vector<vector<int>> dp(frame);
//         int row = dp.size(), col = dp[0].size();

//         for(int i = 0 ; i < row ; i++)
//         {
//             for(int j = 0 ; j < col ; j++)
//             {
//                 int left = 0, up = 0;
//                 if(i > 0) up = dp[i-1][j];
//                 if(j > 0) left = dp[i][j-1];
//                 dp[i][j] = frame[i][j] + max(left, up);
//             }
//         }

//         return dp[row-1][col-1];
//     }
// };

// 动态规划8
// class Solution {
// public:
//     inline int getMin(int a, int b, int c)
//     {
//         return min(a,b) > c ? c : min(a,b);
//     }

//     int minFallingPathSum(vector<vector<int>>& matrix) {
//         vector<vector<int>> dp(matrix);
//         int n = dp.size();
//         if(n == 1) return matrix[0][0];

//         int min = INT_MAX;
//         for(int i = 1 ; i < n ; i++)
//         {
//             for(int j = 0 ; j < n ; j++)
//             {
//                 int upleft = INT_MAX, upright = INT_MAX;
//                 if(j - 1 >= 0) upleft  = dp[i-1][j-1];
//                 if(j + 1 < n)  upright = dp[i-1][j+1];
//                 dp[i][j] = matrix[i][j] + getMin(upleft, dp[i-1][j], upright);

//                 if(i == n - 1)
//                 {
//                     if(min > dp[i][j]) min = dp[i][j];
//                 }
//             }
//         }
//         return min;
//     }
// };

// 动态规划9
// class Solution {
// public:
//     int minPathSum(vector<vector<int>>& grid) {
//         int row = grid.size()+1, col = grid[0].size()+1;
//         vector<vector<int>> dp(row,vector<int>(col,INT_MAX));
//         dp[row-1][col-2] = 0;

//         for(int i = row-2 ; i >= 0 ; i--)
//         {
//             for(int j = col-2 ; j >= 0 ; j--)
//                 dp[i][j] = grid[i][j] + min(dp[i][j+1], dp[i+1][j]);
//         }
//         return dp[0][0];
//     }
// };

// 动态规划10
// class Solution {
// public:
//     int calculateMinimumHP(vector<vector<int>>& dungeon) {
//         int m = dungeon.size(), n = dungeon[0].size();
//         vector<vector<int>> dp(m+1, vector<int>(n+1, INT_MAX));
//         dp[m][n-1] = 1;

//         for(int i = m-1 ; i >= 0 ; i--)
//         {
//             for(int j = n-1 ; j >= 0 ; j--)
//             {
//                 dp[i][j] = min(dp[i][j+1], dp[i+1][j]) - dungeon[i][j];
//                 // dungeon[i][j]很大时，会导致dp[i][j]为负数
//                 // 但是dp[i][j]小于0不能成为初始HP值，所以至少置为1
//                 dp[i][j] = max(1, dp[i][j]);
//             }
//         }

//         return dp[0][0];
//     }
// };

// 动态规划11
// class Solution {
// public:
//     int massage(vector<int>& nums) {
//         int n = nums.size();
//         if(n == 0) return 0;
//         vector<int> f(n); // f[i]表示nums[0,i]序列的最长预约时间, nums[i]选
//         vector<int> g(n); // g[i]表示nums[0,i]序列的最长预约时间, nums[i]不选
//         f[0] = nums[0];
//         for(int i = 1 ; i < n ; i++)
//         {
//             f[i] = nums[i] + g[i-1];
//             g[i] = max(f[i-1], g[i-1]);
//         }
//         return max(f[n-1], g[n-1]);
//     }
// };

// 动态规划12
// class Solution {
// public:
//     int rob1(vector<int>& nums) {
//         int n = nums.size();
//         if(n == 0) return 0;
//         vector<int> f(n); // f[i]表示nums[0,i]序列的最高金额, nums[i]偷
//         vector<int> g(n); // g[i]表示nums[0,i]序列的最高金额, nums[i]不偷
//         f[0] = nums[0];
//         for(int i = 1 ; i < n ; i++)
//         {
//             f[i] = nums[i] + g[i-1];
//             g[i] = max(f[i-1], g[i-1]);
//         }
//         return max(f[n-1], g[n-1]);
//     }

//     int rob(vector<int>& nums) {
//         if(nums.size() == 0) return 0;
//         if(nums.size() == 1) return nums[0];
//         if(nums.size() == 2) return max(nums[0],nums[1]);

//         vector<int> n1(nums.begin()+2, nums.end()-1);
//         vector<int> n2(nums.begin()+1,nums.end());

//         return max(nums[0]+rob1(n1), rob1(n2));
//     }
// };


// 动态规划13
// class Solution {
// public:
//     // int deleteAndEarn(vector<int>& nums) {
//     //     sort(nums.begin(), nums.end());
//     //     int n = nums.size();
//     //     vector<int> f(n), g(n);
//     //     f[0] = nums[0], g[0] = 0;

//     //     int i = 0, j = 0;
//     //     while(i < n)
//     //     {
//     //         if(i > 0)
//     //         {
//     //             // 两组重复数的边界处，如：(2,2,2,3,3)
//     //             if(nums[i-1] == nums[i] - 1) // 前一个删了会影响当前的
//     //                 f[i] = g[i-1] + nums[i];
//     //             else // 前一个删了不会影响当前的
//     //                 f[i] = max(f[i-1], g[i-1]) + nums[i];
                
//     //             g[i] = max(f[i-1], g[i-1]);
//     //         }
//     //         for(j = ++i ; j < n && nums[j] == nums[j-1] ; j++)
//     //         {
//     //             f[j] = f[j-1] + nums[j];
//     //             g[j] = g[j-1];
//     //         }
//     //         i = j;
//     //     }

//     //     return max(f[n-1], g[n-1]);
//     // }

//     int deleteAndEarn(vector<int>& nums) {
//         // 空间换时间
//         // 用一个数组映射nums（下标为nums[i], 内容为nums[i]的在nums中的总和）
//         const int N = 10001;
//         int arr[N] = {0};
//         for(auto n : nums) arr[n] += n;

//         // 在arr中解决一次“打家劫舍”问题
//         vector<int> f(N), g(N);
//         for(int i = 1 ; i < N ; i++)
//         {
//             f[i] = arr[i] + g[i-1];
//             g[i] = max(f[i-1], g[i-1]);
//         }
//         return max(f[N-1], g[N-1]);
//     }
// };

// 动态规划14
// class Solution {
// public:
//     // enum COLOR {RED, BLUE, GREEN};

//     // int minIn3(int a, int b, int c)
//     // {
//     //     int tmp = min(a, b);
//     //     return tmp > c ? c : tmp;
//     // }

//     // int minCost(vector<vector<int>>& costs) {
//     //     int n = costs.size();
//     //     vector<int> f(n);
//     //     auto g(f), h(f);
//     //     // dp 粉刷到第i个房子时的最低成本
//     //     // f i红色
//     //     // g i蓝色
//     //     // h i绿色
//     //     f[0] = costs[0][RED], g[0] = costs[0][BLUE], h[0] = costs[0][GREEN];
//     //     if(n == 0) return minIn3(f[0], g[0], h[0]);

//     //     for(int i = 1 ; i < n ; i++)
//     //     {
//     //         f[i] = costs[i][RED] + min(g[i-1], h[i-1]);
//     //         g[i] = costs[i][BLUE] + min(f[i-1], h[i-1]);
//     //         h[i] = costs[i][GREEN] + min(f[i-1], g[i-1]);
//     //     }
//     //     return minIn3(f[n-1], g[n-1], h[n-1]);
//     // }

//     int minCost(vector<vector<int>>& costs){
//         int n = costs.size();
//         if(n == 0) return min(costs[0][0], min(costs[0][1], costs[0][2]));
//         vector<vector<int>> dp(costs);
//         for(int i = 1 ; i < n ; i++)
//         {
//             dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2]);
//             dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2]);
//             dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1]);
//         }
//         return min(dp[n-1][0], min(dp[n-1][1], dp[n-1][2]));
//     }
// };


// 动态规划17 -- 买卖股票三
// class Solution {
// public:
//     const int INF = 0x3f3f3f3f;
//     int maxProfit(vector<int>& prices) {
//         int n = prices.size();
//         int m = 2; // 最大可完成交易次数
//         vector<vector<int>> f(n, vector<int>(m+1));
//         vector<vector<int>> g(n, vector<int>(m+1));

//         f[0][0] = -prices[0], f[0][1] = f[0][2] = -INF;
//         g[0][0] = 0, g[0][1] = g[0][2] = -INF;

//         for(int i = 1 ; i < n ; i++)
//         {
//             // j表示已完成交易次数 (0, 1, 2)
//             for(int j = 0 ; j <= m ; j++)
//             {
//                 f[i][j] = max(f[i-1][j], g[i-1][j] - prices[i]);

//                 if(j > 0)
//                     g[i][j] = max(g[i-1][j], f[i-1][j-1] + prices[i]);
//                 else
//                     g[i][j] = g[i-1][j];
//             }
//         }

//         return max(g[n-1][0], max(g[n-1][1], g[n-1][2]));
//     }
// };

// 动态规划18 -- 买卖股票四
// class Solution {
// public:
//     int maxProfit(int k, vector<int>& prices) {
//         int n = prices.size();
//         vector<vector<int>> f(n, vector<int>(k+1, -0x3f3f3f3f));
//         vector<vector<int>> g(n, vector<int>(k+1, -0x3f3f3f3f));

//         f[0][0] = -prices[0];
//         g[0][0] = 0;

//         for(int i = 1 ; i < n ; i++)
//         {
//             // j表示已完成交易次数 (0, 1, 2)
//             for(int j = 0 ; j <= k ; j++)
//             {
//                 f[i][j] = max(f[i-1][j], g[i-1][j] - prices[i]);

//                 if(j > 0)
//                     g[i][j] = max(g[i-1][j], f[i-1][j-1] + prices[i]);
//                 else
//                     g[i][j] = g[i-1][j];
//             }
//         }

//         int ans = g[n-1][0];
//         for(auto& p : g[n-1])
//         {
//             if(p > ans)
//                 ans = p;
//         }        
//         return ans;
//     }
// };

// 动态规划21
// class Solution {
// public:
//     int maxProduct(vector<int>& nums) {
//         int n = nums.size();
//         vector<vector<int>> dp(2,vector<int>(n));
//         dp[0][0] = dp[1][0] = nums[0];
//         //dp[0]: 以i结尾的所有子数组的最大乘积
//         //dp[1]: 以i结尾的所有子数组的最小乘积
//         // 正*大=大   负*小=大

//         int ret = dp[0][0];
//         for(int i = 1 ; i < n ; i++)
//         {
//             // if(nums[i] > 0)
//             // {
//             //     dp[0][i] = max(nums[i], nums[i] * dp[0][i-1]);
//             //     dp[1][i] = min(nums[i], nums[i] * dp[1][i-1]);
//             // }
//             // else if(nums[i] < 0)
//             // {
//             //     dp[0][i] = max(nums[i], nums[i] * dp[1][i-1]);
//             //     dp[1][i] = min(nums[i], nums[i] * dp[0][i-1]);
//             // }

//             dp[0][i] = max(nums[i], max(nums[i] * dp[0][i-1], nums[i] * dp[1][i-1]));
//             dp[1][i] = min(nums[i], min(nums[i] * dp[0][i-1], nums[i] * dp[1][i-1]));

//             ret = max(ret, dp[0][i]);
//         }

//         return ret;
//     }
// };

// 动态规划22
// class Solution {
// public:
//     int getMaxLen(vector<int>& nums) {
//         int n = nums.size();
//         vector<int> f(n+1);//以i结尾乘积为正数的最长子数组长度
//         auto g(f);//以i结尾乘积为负数的最长子数组长度
//         int ret = 0;
//         for(int i = 1 ; i <= n ; i++)
//         {
//             if(nums[i-1] > 0)
//             {
//                 f[i] = 1 + f[i-1];
//                 g[i] = g[i-1] > 0 ? 1 + g[i-1] : 0;
//             }
//             else if(nums[i-1] < 0)
//             {
//                 g[i] = 1 + f[i-1];
//                 f[i] = g[i-1] > 0 ? 1 + g[i-1] : 0;
//             }
//             ret = max(f[i], ret);
//         }
//         return ret;
//     }
// };

// 动态规划23
// class Solution {
// public:
//     int numberOfArithmeticSlices(vector<int>& nums) {
//         int n = nums.size();
//         if(n < 3) return 0;
//         vector<int> dp(n);
//         int ret = 0;
//         for(int i = 2 ; i < n ; i++)
//         {
//             if(nums[i] + nums[i-2] == 2 * nums[i-1]) // 等差数列的性质
//                 dp[i] = 1 + dp[i-1];
//             ret += dp[i];
//         }
//         return ret;
//     }
// };

// 动态规划24
// class Solution {
// public:
//     int maxTurbulenceSize(vector<int>& arr) {
//         int n = arr.size();
//         if(n == 1) return 1;

//         vector<int> dp(n);
//         dp[0] = 1;
//         dp[1] = arr[0] == arr[1] ? 1 : 2;
//         int ret = dp[1];
//         for(int i = 2 ; i < n ; i++)
//         {
//             int a = arr[i-2], b = arr[i-1], c = arr[i];
//             if((a>b && b<c) || (a<b && b>c))
//                 dp[i] = dp[i-1] + 1;
//             else if(b == c)
//                 dp[i] = 1;
//             else
//                 dp[i] = 2;

//             ret = max(ret, dp[i]);
//         }
//         return ret;
//     }
// };

// 动态规划25
// class Solution {
// public:
//     bool inWordDict(string word, vector<string>& wordDict)
//     {
//         for(auto& w : wordDict)
//         {
//             if(w == word) return true;
//         }
//         return false;
//     }
//     bool wordBreak(string s, vector<string>& wordDict) {
//         int n = s.size();
//         vector<bool> dp(n);

//         for(int i = 0 ; i < n ; i++)
//         {
//             for(int j = i ; j >= 0 ; j--)
//             {
//                 string curWord = s.substr(j, i+1-j);
//                 if(inWordDict(curWord, wordDict))
//                 {
//                     if(j == 0 || dp[j-1] == true) 
//                         dp[i] = true;
//                 }
//             }
//         }

//         return dp[n-1];
//     }
// };

// 动态规划26
// class Solution {
// public:
//     int findSubstringInWraproundString(string s) {
//         int n = s.size();
//         vector<int> dp(n,1);
//         vector<int> maxCounter(26);
//         maxCounter[s[0] - 'a'] = 1; // 保存以'a'-'z'结尾的且在base中出现的最大子串数
//         for(int i = 1 ; i < n ; i++)
//         {
//             if(s[i] - s[i-1] == 1 || (s[i] == 'a' && s[i-1] == 'z')) 
//                 dp[i] += dp[i-1];
                
//             maxCounter[s[i] - 'a'] = max(maxCounter[s[i] - 'a'], dp[i]);
//         }
//         int ret = 0;
//         for(auto& e : maxCounter) ret += e;
//         return ret;
//     }
// };